package datastructure.stack;


public class StactDemo {
    // 括号匹配
    public static boolean isValid(String reg) {
        MyStack<Character> stack = new MyArrayStack<>();
        /**
         * 分析: 我们这样想: 遍历字符串得到每一个字符,如果是左括号就入栈, 不是就进行弹栈,
         * 判断弹栈出来的元素和遍历元素是不是匹配的,如果不匹配就返回false 最后判断栈是否为空, 为null--说明匹配
         */
        for (int i = 0; i < reg.length(); i++) {
            char ch = reg.charAt(i);
            if (ch == '[' || ch == '(' || ch == '{') {
                stack.push(ch);
            } else {
                if (stack.isEmpty()) {
                    return false;
                }
                // 栈不为空时候
                Character topChar = stack.pop();
                if (topChar == '(' && ch != ')') {
                    return false;
                }
                if (topChar == '[' && ch != ']') {
                    return false;
                }
                if (topChar == '{' && ch != '}') {
                    return false;
                }
            }
        }

        return stack.isEmpty();
    }

    public static void main(String[] args) {
        String str = "({[][]][})";
        isValid(str);
    }
}
